package com.wss.lsl.test.driven.arithmetic;

/**
 * 寻找最大子数组。线性解法
 * 
 * @author weiss
 *
 */
public class FindMaxImumSubArray2 {

	public static int[] findMaxImumSubArray(int[] data, int low) {
		int sum = 0;
		int maxLeft = -1;
		int maxRight = -1;
		int maxSum = 0;

		if (data.length == 0) {
			return new int[] { -1, -1, 0 };
		}
		sum = data[0];
		maxSum = sum;
		maxLeft = 0;
		maxRight = maxLeft;
		for (int i = 0; i < data.length; i++) {
			sum = data[i];
			if (sum > maxSum) {
				maxSum = sum;
				maxLeft = i;
				maxRight = maxLeft;
			}
			for (int j = i + 1; j < data.length; j++) {
				sum += data[j];
				if (sum > maxSum) {
					maxSum = sum;
					maxRight = j;
				}
			}
		}
		return new int[] { maxLeft, maxRight, maxSum };
	}
}
